package datastruct;

import java.util.Stack;

/**
 * @author 23050
 * @version 1.0
 * @description: TODO
 * @date 2023/12/8 19:33
 */
public class Sort {

    /**
     * 时间复杂度：
     *   最好情况，数据完全有序的时候O(N)
     *   最坏情况：数据完全逆序的情况下O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定排序
     *
     * 数据越有序，排序越快
     *
     */
    public static void insertSort(int[] array){
        for(int i = 1;i< array.length;i++){
            int tmp = array[i];
            int j = i-1;
            for(;j>=0;j--){
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }







    /**
     *
     * 时间复杂度：
     *  gap不同，时间复杂度不同  一般是O(N^1.3)--O(N^1.5)
     *
     * 不稳定的排序
     * 空间负责度O(1)
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap>1) {
            gap /= 2;
            //每一个gap进行选择排序
            shell(array, gap);
        }

    }
    public static void shell(int[] array,int gap){
        for(int i = gap;i< array.length;i++){
            int tmp = array[i];
            int j = i-gap;
            for(;j>=0;j-=gap){
                if (array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }





    /**
     *
     * 时间复杂度：
     *  不管最好还是最坏，都是O(N^2)
     * 空间复杂度：O(1)
     * 不稳定的
     *
     *
     */

    public static void selectSort(int[] array){

        for(int i = 0;i<array.length ; i++){
            int minIndex = i;
            for(int j = i ;j< array.length;j++){
                if (array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left<right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1;i<=right;i++){
                if (array[i]>array[maxIndex]){
                    maxIndex = i;
                }
                if (array[i]<array[minIndex]){
                    minIndex = i;
                }
            }
            swap(array,left,minIndex);

            //最大值刚好在最小值的位置，已经交换到了minindex了
            if (maxIndex == left){
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            right--;
            left++;
        }

    }


    public static void swap(int[] array,int i,int minIndex){
        int tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
    }




    /**
     * 时间复杂度
     *  O(N) + O(NlogN)
     * 空间复杂度
     *  O(1)
     * 稳定性：不稳定
     */
    public static void heapSort(int[] array){
        //建立大根堆
        createBigHeap(array);

        int end = array.length-1;
        while (end >0){
            //依次把最大值换到最后
            swap(array,0,end);
            //将剩下的元素继续调整成大根堆
            siftDown(array,0,end);
            end--;
        }


    }
    //创建大根堆
    private static void createBigHeap(int[] array){
        for(int parent = (array.length-1-1/2);parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }

    //向下调整
    private static void siftDown(int[] array,int parent,int end){
        int child = 2*parent+1;
        while (child<end){
            if (child+1<end && array[child] <array[child+1]){
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }





    /**
     * 时间复杂度
     *   最好O(N)
     *   最坏O(N^2)
     * 空间复杂度 O(1)
     * 稳定性：稳定
     */
    public static void bubbleSort(int[] array){
        for(int i = 0;i<array.length-1;i++){
            int flag = 0;
            for(int j = 0;j<array.length-1-i;j++){
                if (array[j]>array[j+1]){
                    flag = 1;
                    swap(array,j,j+1);
                }
            }
            if (flag == 0){
                break;
            }
        }
    }



    /**
     * 时间复杂度：
     *   最好：O(N*logN)
     *   最坏：O(N^2)
     * 空间复杂度：
     *   最好：O(logN)
     *   最坏：O(N)
     * 稳定性：不稳定
     * 这种情况下数据量大的时候可能会溢出
     */
    public static void quickSort(int[] array){
        quick(array,0,array.length - 1);

    }
    public static void quick(int[] array,int start,int end){
        //递归出口
        if (start >= end){
            return;
        }

        //当元素最多只有15的时候进行插入排序
        if ((end-start+1)<=15){
            insertSortRange(array,start,end);
            return;
        }

        //三数取中  优化
        int index = midOfThree(array,start,end);
        //保证start下标是中间大的数字
        swap(array,index,start);

        //找到基准值
        int pivot = partition(array,start,end);
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,start+1,end);

    }

    private static void insertSortRange(int[] array, int begin, int end) {
            for(int i = begin;i<=end;i++){
                int tmp = array[i];
                int j = i-1;
                for(;j>=begin;j--){
                    if (array[j] > tmp){
                        array[j+1] = array[j];
                    }else{
                        break;
                    }
                }
                array[j+1] = tmp;
            }

    }

    //三数取中
    private static int midOfThree(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if (array[left]<array[right]){
            if (array[mid]<array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if (array[mid]>array[left]){
                return left;
            }else if(array[mid]<array[right]){
                return right;
            }else{
                return mid;
            }

        }
    }

/*    private static int partition(int[] array,int left,int right){
        int prev = left;
        int cur = left+1;
        while (cur<=right){
            if (array[cur]<array[left] && array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }*/






    //非递归
    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        //找最后的位置
        int pivot = partition(array, left, right);
        //将左右区间放到栈里
        if (pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty() ){
            right = stack.pop();
            left = stack.pop();

            //找基准值，三数取中
            pivot = partition(array, left, right);
            //将左右区间放到栈里
            if (pivot-1>left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right){
                stack.push(pivot+1);
                stack.push(right);
            }
        }

    }

    private static int partition(int[] array,int left,int right){
        int key = array[left];
        while (left < right){
            while (left<right && array[right] >= key ){
                right--;
            }
            array[left] = array[right];

            while (left<right && array[left] <= key){
                left++;
            }
            array[right] = array[left];

        }
        array[left] = key;
        return left;
    }




    /**
     * 时间复杂度：O(N*logN)
     * 空间负责度：O(N)
     * 稳定性：稳定
     */
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }

    private static void mergeSortFunc(int[] array, int left, int right){
        if (left>=right){
            return;
        }
        int mid = (left+right)/2;

        //分组
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);

        //排序+合并
        merge(array,left,right,mid);

    }

    private static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;

        int[] tmp = new int[right-left+1];
        int k = 0;
        //两个区间都是有数据的
        while (s1<=mid && s2<=right){
            if (array[s1]<=array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        while (s1<=mid){
            tmp[k++] = array[s1++];
        }
        while (s2<=right) {
            tmp[k++] = array[s2++];
        }

        //合并
        for(int i = 0;i<tmp.length;i++){
            array[i+left] = tmp[i];
        }

    }


    public static void mergeSortNor(int[] array){
        int gap = 1;
        while (gap < array.length){
            for(int i = 0;i<array.length;i+=2*gap){
                int left = i;
                int mid = left+gap-1;
                int right = mid+gap;

                if (mid>=array.length){
                    mid = array.length-1;
                }
                if (right >= array.length){
                    right = array.length-1;
                }

                merge(array,left,right,mid);
            }
            gap*=2;
        }

    }






}
